The Maze

Description#

The maze is a puzzle game where the ball moves in the available empty spaces. The player aims to get the ball to the specified destination. The ball can go through the empty spaces by rolling up, down, left, or right, but it will not stop rolling until it hits a wall or reaches the destination and then hits a wall or reaches the end of a grid. After hitting a wall, the ball will choose the next direction before moving forward. The borders of the maze are considered walls.

Constraints#

• maze[i][j] must be 0 or 1, initially.
• mazeLength == maze.length
• mazeSubarrayLength == maze[i].length
• 1 <= mazeLength, mazeSubarrayLength <= 100
• start.length, end.length == 2
• 0 <= $start_{row}$, $end_{row}$ <= mazeLength
• 0 <= $start_{col}$, $end_{col}$ <= mazeSubarrayLength
• The ball and the destination must exist in an empty space and, initially, they will not be in the same position.
• The maze must contain at least two empty spaces.

Let’s see how the maze game looks in the illustration below:

Coding exercise#

Solution#

We can consider the given maze as a depth-first search tree. The starting position will represent the root node of the tree. We will choose one path at a time and try to go as deep as possible into the levels of the tree before opting for the next path. We will have four possible directions on each position, that is, left, right, up, or down, except for the borders of the maze. Thus, the ball will start traversing from the root node over the branch, and the new position will be represented as an empty space or a wall.

Let’s see the following algorithm to implement the described problem.

1. We are given a 2D array named maze.

2. We are also given the coordinates of a start and end cell. We will use a hash map named visited_places to keep track of the cells that have already been visited.

3. We will move continuously in either the left, right, upward, or downward direction from every starting position till we reach the boundary or a wall.

4. The empty space is represented by 0, a wall is represented by 1.

5. From the starting position, we will determine all the endpoints that can be reached by choosing the four directions. For each case, the new endpoint will act as the new starting point for the traversals.

6. When we move to the next empty space in any direction, we will update the current index value in the visited_places to True.

7. We will call the path function in each direction recursively, and each time we will use the previously obtained starting point.

8. At the end, when the starting position and the destination are the same, we will return True. Otherwise, we will update the current position in the visited_places to True and return False.

Let’s understand this algorithm with the illustration given below:

Let’s look at the solution below:

Complexity measures#

Time complexity#

We will traverse the complete maze in the worst-case scenario, so the time complexity will be $O(mn)$, wherein $[m]$ will be the size of the row and $[n]$ will be the size of the column.

Space complexity#

In the worst-case scenario, the call stack depth will be $O(m*n)$. Therefore, the space complexity will be $O(mn)$.